Vertex coloring complete multipartite graphs from random lists of size 2

Let K_s×m be the complete multipartite graph with s parts and m vertices in each part. Assign to each vertex v of K_s×m a list L(v) of colors, by choosing each list uniformly at random from all 2-subsets of a color set C of size σ(m). In this paper we determine, for all fixed s and growing m, the asymptotic probability of the existence of a proper coloring φ, such that φ(v)∈L(v) for all v∈V(K_s×m). We show that this property exhibits a sharp threshold at σ(m)=2(s−1)m.     

3-list-coloring planar graphs of girth 4

In Thomassen (1995) [4], Thomassen proved that planar graphs of girth at least 5 are 3-choosable. In Li (2009) [3], Li improved Thomassen’s result by proving that planar graphs of girth 4 with no 4-cycle sharing a vertex with another 4- or 5-cycle are 3-choosable. In this paper, we prove that planar graphs of girth 4 with no 4-cycle sharing an edge with another 4- or 5-cycle are 3-choosable. It is clear that our result strengthens Li’s result.     

若干圈的广义冠图的2-强边染色

本文研究了圈的广义冠图CmFn,CmWn,CmCn的2-强边染色(D(2)-点可区别边染色).利用穷染、递推的方法得到了CmFn,CmWn,CmCn的2-强边色数(D(2)-点可区别边色数),并给出一种染色方案,推广了参考文献[6,7]的相应结果.     

Equitable edge‐colorings of simple graphs

An edge‐coloring of a graph G is equitable if, for each v∈V(G), the number of edges colored with any one color incident with v differs from the number of edges colored with any other color incident with v by at most one. A new sufficient condition for equitable edge‐colorings of simple graphs is obtained. This result covers the previous results, which are due to Hilton and de Werra, verifies a conjecture made by Hilton recently, and substantially extends it to a more general class of graphs. © 2010 Wiley Periodicals, Inc. J Graph Theory 66:175‐197, 2011     

A new type of edge-derived vertex coloring

We study the minimum number of weights assigned to the edges of a graph G with no component K₂ so that any two adjacent vertices have distinct sets of weights on their incident edges. The best possible upper bound on this parameter is proved.     

Efficient algorithms for wavelength assignment on trees of rings

A fundamental problem in communication networks is wavelength assignment (WA): given a set of routing paths on a network, assign a wavelength to each path such that the paths with the same wavelength are edge-disjoint, using the minimum number of wavelengths. The WA problem is NP-hard for a tree of rings network which is well used in practice. In this paper, we give an efficient algorithm which solves the WA problem on a tree of rings with an arbitrary (node) degree using at most 3L wavelengths and achieves an approximation ratio of 2.75 asymptotically, where L is the maximum number of paths on any link in the network. The 3L upper bound is tight since there are instances of the WA problem that require 3L wavelengths even on a tree of rings with degree four. We also give a 3L and 2-approximation (resp. 2.5-approximation) algorithm for the WA problem on a tree of rings with degree at most six (resp. eight). Previous results include: 4L (resp. 3L) wavelengths for trees of rings with arbitrary degrees (resp. degree at most eight), and 2-approximation (resp. 2.5-approximation) algorithm for trees of rings with degree four (resp. six).     

Planar graphs with maximum degree 8 and without adjacent triangles are 9-totally-colorable

The Total Coloring Conjecture, in short, TCC, says that every simple graph is (Δ+2)-totally-colorable where Δ is the maximum degree of the graph. Even for planar graphs this conjecture has not been completely settled yet. However, every planar graph with Δ≥9 has been proved to be (Δ+1)-totally-colorable. In this paper, we prove that planar graphs with maximum degree 8 and without adjacent triangles are 9-totally-colorable.     

Mycielski图的BBC染色

基于图G的Mycielski图M（G）,研究xb（G,TG）与xb（M（G）,T’）之间的关系以及xb（G,TG）与xb（M（G）,T＂）之间的关系,其中Tc为G的生成树,T’,T＂分别为M（G）的两类特殊生成树．并给出当G为二部图,完全图以及Halin图时,Xb（M（G）,T＂）的值．     

图的邻点可区别全色数的一个上界

Let G = （V, E） be a simple connected graph, and ｜V（G）｜ ≥ 2. Let f be a mapping from V（G） ∪ E（G） to {1,2…, k}. If arbitary uv ∈ E（G）,f（u） ≠ f（v）,f（u） ≠ f（uv）,f（v） ≠ f（uv）; arbitary uv, uw ∈ E（G）（v ≠ w）, f（uv） ≠ f（uw）;arbitary uv ∈ E（G） and u ≠ v, C（u） ≠ C（v）, where
C（u）={f（u）}∪{f（uv）｜uv∈E（G）}.
Then f is called a k-adjacent-vertex-distinguishing-proper-total coloring of the graph G（k-AVDTC of G for short）. The number min{k｜k-AVDTC of G} is called the adjacent vertex-distinguishing total chromatic number and denoted by χat（G）. In this paper we prove that if △（G） is at least a particular constant and δ ≥32√△ln△, then χat（G） ≤ △（G） ＋ 10^26 ＋ 2√△ln△.